home *** CD-ROM | disk | FTP | other *** search
/ BCI NET / BCI NET Dec 94.iso / archives / programming / c / gcc222-3.lha / const_class / sllist.ccp < prev    next >
Encoding:
Text File  |  1993-02-04  |  5.1 KB  |  292 lines
  1. // This may look like C code, but it is really -*- C++ -*-
  2. /* 
  3. Copyright (C) 1988 Free Software Foundation
  4.     written by Doug Lea (dl@rocky.oswego.edu)
  5.  
  6. This file is part of the GNU C++ Library.  This library is free
  7. software; you can redistribute it and/or modify it under the terms of
  8. the GNU Library General Public License as published by the Free
  9. Software Foundation; either version 2 of the License, or (at your
  10. option) any later version.  This library is distributed in the hope
  11. that it will be useful, but WITHOUT ANY WARRANTY; without even the
  12. implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  13. PURPOSE.  See the GNU Library General Public License for more details.
  14. You should have received a copy of the GNU Library General Public
  15. License along with this library; if not, write to the Free Software
  16. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  17. */
  18.  
  19. #ifdef __GNUG__
  20. #pragma implementation
  21. #endif
  22. #include <values.h>
  23. #include <stream.h>
  24. #include <builtin.h>
  25. #include "<T>.SLList.h"
  26.  
  27. void <T>SLList::error(const char* msg)
  28. {
  29.   (*lib_error_handler)("SLList", msg);
  30. }
  31.  
  32. int <T>SLList::length()
  33. {
  34.   int l = 0;
  35.   <T>SLListNode* t = last;
  36.   if (t != 0) do { ++l; t = t->tl; } while (t != last);
  37.   return l;
  38. }
  39.  
  40. <T>SLList::<T>SLList(const <T>SLList& a)
  41. {
  42.   if (a.last == 0)
  43.     last = 0;
  44.   else
  45.   {
  46.     <T>SLListNode* p = a.last->tl;
  47.     <T>SLListNode* h = new <T>SLListNode(p->hd);
  48.     last = h;
  49.     for (;;)
  50.     {
  51.       if (p == a.last)
  52.       {
  53.         last->tl = h;
  54.         return;
  55.       }
  56.       p = p->tl;
  57.       <T>SLListNode* n = new <T>SLListNode(p->hd);
  58.       last->tl = n;
  59.       last = n;
  60.     }
  61.   }
  62. }
  63.  
  64. <T>SLList& <T>SLList::operator = (const <T>SLList& a)
  65. {
  66.   if (last != a.last)
  67.   {
  68.     clear();
  69.     if (a.last != 0)
  70.     {
  71.       <T>SLListNode* p = a.last->tl;
  72.       <T>SLListNode* h = new <T>SLListNode(p->hd);
  73.       last = h;
  74.       for (;;)
  75.       {
  76.         if (p == a.last)
  77.         {
  78.           last->tl = h;
  79.           break;
  80.         }
  81.         p = p->tl;
  82.         <T>SLListNode* n = new <T>SLListNode(p->hd);
  83.         last->tl = n;
  84.         last = n;
  85.       }
  86.     }
  87.   }
  88.   return *this;
  89. }
  90.  
  91. void <T>SLList::clear()
  92. {
  93.   if (last == 0)
  94.     return;
  95.  
  96.   <T>SLListNode* p = last->tl;
  97.   last->tl = 0;
  98.   last = 0;
  99.  
  100.   while (p != 0)
  101.   {
  102.     <T>SLListNode* nxt = p->tl;
  103.     delete(p);
  104.     p = nxt;
  105.   }
  106. }
  107.  
  108.  
  109. Pix <T>SLList::prepend(<T&> item)
  110. {
  111.   <T>SLListNode* t = new <T>SLListNode(item);
  112.   if (last == 0)
  113.     t->tl = last = t;
  114.   else
  115.   {
  116.     t->tl = last->tl;
  117.     last->tl = t;
  118.   }
  119.   return Pix(t);
  120. }
  121.  
  122.  
  123. Pix <T>SLList::prepend(<T>SLListNode* t)
  124. {
  125.   if (t == 0) return 0;
  126.   if (last == 0)
  127.     t->tl = last = t;
  128.   else
  129.   {
  130.     t->tl = last->tl;
  131.     last->tl = t;
  132.   }
  133.   return Pix(t);
  134. }
  135.  
  136.  
  137. Pix <T>SLList::append(<T&> item)
  138. {
  139.   <T>SLListNode* t = new <T>SLListNode(item);
  140.   if (last == 0)
  141.     t->tl = last = t;
  142.   else
  143.   {
  144.     t->tl = last->tl;
  145.     last->tl = t;
  146.     last = t;
  147.   }
  148.   return Pix(t);
  149. }
  150.  
  151. Pix <T>SLList::append(<T>SLListNode* t)
  152. {
  153.   if (t == 0) return 0;
  154.   if (last == 0)
  155.     t->tl = last = t;
  156.   else
  157.   {
  158.     t->tl = last->tl;
  159.     last->tl = t;
  160.     last = t;
  161.   }
  162.   return Pix(t);
  163. }
  164.  
  165. void <T>SLList::join(<T>SLList& b)
  166. {
  167.   <T>SLListNode* t = b.last;
  168.   b.last = 0;
  169.   if (last == 0)
  170.     last = t;
  171.   else if (t != 0)
  172.   {
  173.     <T>SLListNode* f = last->tl;
  174.     last->tl = t->tl;
  175.     t->tl = f;
  176.     last = t;
  177.   }
  178. }
  179.  
  180. Pix <T>SLList::ins_after(Pix p, <T&> item)
  181. {
  182.   <T>SLListNode* u = (<T>SLListNode*)p;
  183.   <T>SLListNode* t = new <T>SLListNode(item);
  184.   if (last == 0)
  185.     t->tl = last = t;
  186.   else if (u == 0) // ins_after 0 means prepend
  187.   {
  188.     t->tl = last->tl;
  189.     last->tl = t;
  190.   }
  191.   else
  192.   {
  193.     t->tl = u->tl;
  194.     u->tl = t;
  195.     if (u == last) 
  196.       last = t;
  197.   }
  198.   return Pix(t);
  199. }
  200.  
  201.  
  202. void <T>SLList::del_after(Pix p)
  203. {
  204.   <T>SLListNode* u = (<T>SLListNode*)p;
  205.   if (last == 0 || u == last) error("cannot del_after last");
  206.   if (u == 0) u = last; // del_after 0 means delete first
  207.   <T>SLListNode* t = u->tl;
  208.   if (u == t)
  209.     last = 0;
  210.   else
  211.   {
  212.     u->tl = t->tl;
  213.     if (last == t)
  214.       last = u;
  215.   }
  216.   delete t;
  217. }
  218.  
  219. int <T>SLList::owns(Pix p)
  220. {
  221.   <T>SLListNode* t = last;
  222.   if (t != 0 && p != 0)
  223.   {
  224.     do
  225.     {
  226.       if (Pix(t) == p) return 1;
  227.       t = t->tl;
  228.     } while (t != last);
  229.   }
  230.   return 0;
  231. }
  232.  
  233. <T> <T>SLList::remove_front()
  234. {
  235.   if (last == 0) error("remove_front of empty list");
  236.   <T>SLListNode* t = last->tl;
  237.   <T> res = t->hd;
  238.   if (t == last)
  239.     last = 0;
  240.   else
  241.     last->tl = t->tl;
  242.   delete t;
  243.   return res;
  244. }
  245.  
  246. int <T>SLList::remove_front(<T>& x)
  247. {
  248.   if (last == 0)
  249.     return 0;
  250.   else
  251.   {
  252.     <T>SLListNode* t = last->tl;
  253.     x = t->hd;
  254.     if (t == last)
  255.       last = 0;
  256.     else
  257.       last->tl = t->tl;
  258.     delete t;
  259.     return 1;
  260.   }
  261. }
  262.  
  263.  
  264. void <T>SLList::del_front()
  265. {
  266.   if (last == 0) error("del_front of empty list");
  267.   <T>SLListNode* t = last->tl;
  268.   if (t == last)
  269.     last = 0;
  270.   else
  271.     last->tl = t->tl;
  272.   delete t;
  273. }
  274.  
  275. int <T>SLList::OK()
  276. {
  277.   int v = 1;
  278.   if (last != 0)
  279.   {
  280.     <T>SLListNode* t = last;
  281.     long count = MAXLONG;      // Lots of chances to find last!
  282.     do
  283.     {
  284.       count--;
  285.       t = t->tl;
  286.     } while (count > 0 && t != last);
  287.     v &= count > 0;
  288.   }
  289.   if (!v) error("invariant failure");
  290.   return v;
  291. }
  292.